package com.zhouxianglh.p395;

import java.util.Arrays;

/**
 * 395 至少有K个重复字符的最长子串
 * 使用数组替代map
 *
 * @author zhouxianglh
 */
public class Solution {
    public static int longestSubstring(String s, int k) {
        char[] chars = s.toCharArray();
        //字符串转数组,方便查找
        int[] intChars = new int[chars.length];
        for (int i = 0, j = chars.length; i < j; i++) {
            intChars[i] = chars[i] - 'a';
        }
        //统计出现次数
        int[] intArrCount = new int[26];
        for (int intChar : intChars) {
            intArrCount[intChar]++;
        }
        //最大次数
        int max = 0;
        int[] intArr = new int[26];
        for (int i = 0, j = intChars.length; i < j && (i + max) < j; i++) {
            int flag = 0;
            Arrays.fill(intArr, 0);
            for (int m = i, n = intChars.length; m < n; m++) {
                int c = intChars[m];
                //小于最小次数,跳过
                if (intArrCount[c] < k) {
                    break;
                }
                intArr[c] = intArr[c] + 1;
                flag++;
                if (flag <= max) {
                    break;
                }
                //检查是否符合要求
                boolean booleanFlag = true;
                for (int t : intArr) {
                    if (t != 0 && t < k) {
                        booleanFlag = false;
                        break;
                    }
                }
                if (booleanFlag) {
                    max = flag;
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(longestSubstring("aaabb", 3));
        System.out.println(longestSubstring("ababbc", 2));
        System.out.println(longestSubstring("a", 1));
        System.out.println(longestSubstring("ababacb", 3));

    }
}
